package c01_array;

import java.util.Arrays;

/**
 * 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
 *
 * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class S26 {
    public static void main(String[] args) {
           int[] arr = new int[] {0,0,1,1,1,2,2,3,3,4};
        //    int[] arr = new int[] {1,1,2};
        int len = new S26().removeDuplicates(arr);
        System.out.println(len);
    }
    public int removeDuplicates2(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return 1;
        //这个右面的值 (含) 是重复数据
        int len=0;
        //检验过的部分
        int replace = 1;
        //i  有序不重复部分
        for (int i = 0; i <nums.length; i++) {
            int current = nums[i];
            len++;
            for(int j = i+1;j< nums.length;j++) {
                //发现重复元素
                if(nums[i]==nums[j]) {
                    replace=j+1;
                    //寻找可替代元素
                    while(replace<nums.length&&nums[replace]==current){
                        replace++;
                    }
                    if(replace>=nums.length) {
                        break;
                    }
                    //找到了可替代元素
                    if(replace<nums.length) {
                        nums[j]=nums[replace];
                    }

                }
            }
            if(replace>=nums.length) {
                break;
            }
        }
     //   System.out.println(Arrays.toString(nums));
        return len;
    }
    public int removeDuplicates(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return 1;
        int len=1;
        int left = 0;
        int right =2;
        int lastRightValue = Integer.MIN_VALUE;
        int lastValue = Integer.MIN_VALUE;
        for (int i = 1; i <nums.length; i++) {
            int current = nums[i];
            if(lastValue==Integer.MIN_VALUE) {
                lastValue=current;
            }else if(lastValue==current) {
                continue;
            }else if(lastRightValue==current) {
                lastValue=current;
                continue;
            }else {
                lastValue=current;
            }
           if(current==nums[left]) {
               if (lastRightValue==Integer.MIN_VALUE) {
                   lastRightValue=current;
               }
               while(right<nums.length&&nums[right]==lastRightValue){
                   right++;
               }
               //找到了替换物品
               if(right<nums.length) {
                   lastRightValue=nums[right];
                   nums[i]=nums[right];
                   len++;
                   left++;
               }
           }else {
               len++;
               left++;
               nums[left]=nums[i];
           }
        }
        System.out.println(Arrays.toString(nums));
        return len;
    }
}
